'''
Created on Jun 2, 2009

@author: trevor

To run ParSAP:

First go to the Configuration section of ParSAP and set all of the configuration variables.
If there are remote machines, run: /usr/bin/ppserver.py -a  on each of them.
Then run: python ParSAP.py <num_cities> <height> <width>


'''
import PrintMap
import pp

import copy, os, operator
import sys,time, math, random

class ParSAP(object):
    '''
    Parallel Simulated Annealing
    '''
    def __init__(self,num,ht,wt):
        '''
        Constructor
        '''        
        self.numCities = int(num) #how many cities to use
        self.height = float(ht) #height and width determine the size of the map, for the PNG that is printed out
        self.width = float(wt)
        self.orderedList = dict() #the main, shared copy of the cities for the whole program

    def createRandomCities(self,sd):
        '''
        Fills the dictionary with a list of randomly placed cities. Keys = 0 -> (n-1)
        If seed is 0, current system time is used for seed
        '''
        prng = random.Random()
        if sd != 0:
                prng.seed(sd)
        for i in range(0,self.numCities):
            self.orderedList[i] = ((prng.random()*self.width),(prng.random()*self.height))

    def getLength(self,cities):
        '''
         takes a dictionary of cities, where it assumes keys 0 -> (n-1) are present
        '''
        runningTotal = 0
        x1 = (cities[len(cities)-1])[0] #Start with the very last city
        y1 = (cities[len(cities)-1])[1]
        for i in range(0,len(cities)):
            x2 = (cities[i])[0]  
            y2 = (cities[i])[1]
            
            d = math.sqrt( ((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1)) )  #and compute the distance between (x1,y1) and (x2,y2)
            runningTotal = runningTotal + d
            
            x1 = x2
            y1 = y2
        
        return runningTotal #return the final length of the cycle

    def SA(self,cities,temperature,cooling,hillclimb_only):
        '''
        The Simulated Annealing algorithm
        '''        
        
        localCities = copy.deepcopy(cities) #create a local copy of the cities for modification, without affecting the main copy

        bestLength = self.getLength(localCities)
        
        for numSame in range(0,1000):
            #numSame is used to see if we dont make any changes after 1000 tries. This is 100% arbitrary,
            #but higher numbers tend to mean better results, up to a point.
            
            index = random.randint(0,self.numCities-1)
            tempCity = localCities[index]
            next = random.randint(0,self.numCities-1)
            while(next == index): 
                next = random.randint(0,self.numCities-1)
            localCities[index] = localCities[next]
            localCities[next] = tempCity
            #Here, we select two cities at random and swap them.  Another option is to select the next city
            #in the dictionary, and to use that.  This has its pros and cons.

            tempLength = self.getLength(localCities)
            
            if tempLength < bestLength:
                #Always accept good changes
                bestLength = tempLength
                numSame = 0
                
            else:
                if not hillclimb_only:
                    r = random.random()
                    e = math.exp( -((tempLength - bestLength) / temperature ))
                    #this is the typical way to sometimes select worse results in SA.
                    if r < e:
                        bestLength = tempLength
                        numSame = 0
                    else: #revert to the original configuration. This one wasn't accepted.
                        tempCity = localCities[index]
                        localCities[index] = localCities[next]
                        localCities[next] = tempCity
            
            temperature = cooling * temperature
            #Lower the temperature (cooling is always < 1)
            
        return (localCities,bestLength)
        #Returns a tuple containing the list of cities AND the length.  This is because the work to calculate the length
        #should not be done in the main thread.
    
if __name__ == '__main__':
    '''
    The main program for ParSAP
    '''    
    start_time = time.time()
    if(len(sys.argv) != 4):
        print "Usage: python ParSAP.py <num_cities> <height> <width>"
    
    #### CONFIGURATION HERE ###################
    coolSched = dict({
    0:.95, 
    1:.9999,
    2:.90,
    3:.9999
                    })
    '''
    give each CPU a cooling schedule
    '''
    
    #t0 = (-(int(sys.argv[2])/int(sys.argv[3])) / (int(sys.argv[1])*int(sys.argv[1]))) / math.log(.8)
    t0 = 5
    '''
    Create an initial temperature.  This needs to be worked out - the math here is kind of hand-wavy
    '''
    
    seed = 42
    #seed = 0
    '''
    Set the seed to a value so that you can compare results against the same initial layout of cities.
    if seed == 0, current system time is used as seed
    '''
    
    HillClimb_Only = False
    '''
    For the sake of testing, you can specify Hill Climb Only, which means that only positive changes
    are accepted.  "False" will be Simulated Annealing as usual.
    '''
    
    ppservers=("*",)
    #ppservers = ()
    '''
    Are we using only the local computer? Or is this a cluster. A * means Auto-Discovery mode, or use a tuple of IP addresses
    '''
    
    remoteCPUS = 1
    localCPUS = 0
    '''
    How many CPUs locally and remotely? The system handles these differently
    '''
    #############################
    
    
    numCPUS=remoteCPUS + localCPUS
   
    job_server = pp.Server(ppservers=ppservers,ncpus=localCPUS)
    #tell the job server what to connect to, and how many local cpus to use
    
    print "Starting ParSAP with", numCPUS, " total workers"
    '''
    Set up ParallelPython stuff
    '''
    
    myPSA = ParSAP(sys.argv[1],sys.argv[2],sys.argv[3])
    myPSA.createRandomCities(seed)
    '''
    Create myPSA instance and give it arguments
    Then populated it with the initial configuration of random cities
    '''
        
    best_length = myPSA.getLength(myPSA.orderedList)
    best_cities = copy.deepcopy(myPSA.orderedList)
    #a deepcopy is probably completely unecessary here.
    print "Initial Length of random map: ", best_length
    PrintMap.printImage(myPSA.orderedList, myPSA.height, myPSA.width, "mydwg.orig",best_length)
    '''
    Hold on to the initial map, and print it out to a PNG file.
    '''
    
    
    
    curCPU = 0
    jobs = dict()
    for i in range(0,numCPUS):
        jobs[i] = job_server.submit(myPSA.SA, (best_cities,t0,coolSched[i],HillClimb_Only),(), ("copy","math","random","operator"))
    #Given the number of CPUs we're using, submit some jobs.
    
    
    ###############
    #useful for figuring out which core you're in, on an SMP
    #mycore = open("/proc/%i/stat" % os.getpid()).read().split()[38]
    #print "core:", mycore, "executing stage"
    ################

    sameCount = 0
    
    flag = True
    while flag:
        if(jobs[curCPU].finished):
            #When a job is completed, grab its result, evaluate it to see if the new length is better
            #and either keep it or toss it. Then restart this processor on the current best result
            result = jobs[curCPU]()
            myLength = result[1]
            print "Result length from CPU #:", curCPU, " was: ", myLength
            if myLength < best_length:
                best_cities = result[0]
                best_length = myLength
                sameCount = 0
            else:
                sameCount = sameCount + 1
            print "Giving job to CPU #: ", curCPU, " with length of: ", best_length
            jobs[curCPU] = job_server.submit(myPSA.SA, (best_cities,t0,coolSched[curCPU],HillClimb_Only),(), ("copy","math","random","operator"))
        else:
            #This should probably be some sort of delay or something, so that this process doens't hog a bunch of time.
            #Once the total number of processors is high enough (in cluster mode), this will stop mattering.
            pass
        if sameCount > 50:
            #If we have 50 of the same answer, we quit
            flag = False
        curCPU = operator.mod((curCPU + 1),numCPUS)
        #check up on our CPUs, one at a time.

    
    print "Final Length of map: ", best_length
    PrintMap.printImage(best_cities, myPSA.height, myPSA.width, "mydwg.final",best_length)
    
    job_server.print_stats()
    print "DONE"
